//遍历树
let inOrder = function (root) {
  let res = [];
  let stack = [];
  while (root || stack.length) {
    while (root !== null) {
      stack.push(root);
      root = root.left;
    }
    root = stack.pop();
    res.push(root.val);
    root = root.right;
  }
  return res;
};
let preOrder = function (root) {
  let res = [];
  let stack = [];
  if (root) stack.push(root);
  while (stack.length) {
    let node = stack.pop();
    res.push(node.val);
    node.right && stack.push(node.right);
    node.left && stack.push(node.left);
  }
  return res;
};
let postOrder = (root) => {
  let res = [];
  let stack = [];
  if (root) stack.push(root);
  while (stack.length) {
    let node = stack.pop();
    res.unshift(node.val);
    node.left && stack.push(node.left);
    node.right && stack.push(node.right);
  }
  return res;
};
function add(a, b) {
  if (a === 0) return b;
  if (b === 0) return a;
  let newA = a ^ b;
  let newB = a & (b << 1);
  return add(newA, newB);
}
function getType(obj) {
  if (obj === "null") return null;
  typeof obj === "object"
    ? Object.prototype.toString
        .call(obj)
        .replace("[object ", "")
        .replace("]", "")
    : typeof obj;
}
Array.prototype.myMap = function (callback, _this) {
  let res = [];
  for (let i = 0; i < this.length; i++) {
    res.push(callback.call(_this, this[i], i, this));
  }
  return res;
};
